#include "linked_stack/linked_stack.h"
#include <stdio.h>
#include <string.h>

void trans(Stack *s2, char *str);
int getPriority(char op);
int solve(char *ex, int count);

int main(int argc, char *argv[]) {
  char *ex = "1+2*3+4*5+6";
  Stack *st;
  stack_init(&st, sizeof(char));
  trans(st, ex);
  char expression[100];
  int count = 0;
  while (!stack_empty(st)) {
    expression[count++] = *(char *)stack_top(st);
    stack_pop(st);
  }
  int result = solve(expression, count);
  printf("%s结果是: %d\n", ex, result);
  return 0;
}

// 封装了一个获取运算符优先级的函数，if嵌套太多了。。。
int getPriority(char op) {
  if (op == '+' || op == '-')
    return 1;
  if (op == '*' || op == '/')
    return 2;
  return 0;
}

void trans(Stack *st2, char *ex) {
  // st1用于存放运算符，st2用于存放最终的前缀表达式
  Stack *st1;
  stack_init(&st1, sizeof(char));
  int len = strlen(ex);
  char top;
  // 从右向左遍历
  for (int i = len - 1; i >= 0; i--) {
    // 如果是右括号，直接入栈
    if (ex[i] == ')') {
      stack_push(st1, &ex[i]);
      // 如果是左括号，依次弹出栈顶元素直到遇到右括号
    } else if (ex[i] == '(') {
      while (!stack_empty(st1) && (top = *(char *)stack_top(st1)) != ')') {
        stack_pop(st1);
        stack_push(st2, &top);
      }
      if (!stack_empty(st1)) {
        // 弹出剩余 的右括号
        stack_pop(st1);
      } else {
        printf("括号不匹配\n");
        return;
      }
      // 如果是操作数，直接入栈
    } else if (ex[i] >= '0' && ex[i] <= '9') {
      stack_push(st2, &ex[i]);
    } else {
      // 如果是运算符
      while (1) {
        // 栈空或栈顶为右括号时，直接入栈
        if (stack_empty(st1)) {
          stack_push(st1, &ex[i]);
          break;
        }
        top = *(char *)stack_top(st1);
        if (top == ')') {
          stack_push(st1, &ex[i]);
          break;
        }
        // 优先级高于等于栈顶运算符，直接入栈
        if (getPriority(ex[i]) >= getPriority(top)) {
          stack_push(st1, &ex[i]);
          break;
        } else {
          stack_pop(st1);
          stack_push(st2, &top);
        }
      }
    }
  }

  // 将st1中剩余的运算符依次弹出并存入st2
  while (!stack_empty(st1)) {
    top = *(char *)stack_top(st1);
    stack_pop(st1);
    stack_push(st2, &top);
  }
}

int solve(char *ex, int count) {
  Stack *st1;
  stack_init(&st1, sizeof(int));

  for (int i = count - 1; i >= 0; i--) {
    char ch = ex[i];

    if (ch >= '0' && ch <= '9') {
      int num = ch - '0';
      stack_push(st1, &num);
    } else {
      int a = *(int *)stack_top(st1);
      stack_pop(st1);
      int b = *(int *)stack_top(st1);
      stack_pop(st1);
      int res;

      switch (ch) {
      case '+':
        res = a + b;
        break;
      case '-':
        res = a - b;
        break; // a - b
      case '*':
        res = a * b;
        break;
      case '/':
        res = a / b; // a / b
        break;
      }
      stack_push(st1, &res);
    }
  }

  int ans = *(int *)stack_top(st1);
  stack_pop(st1);
  return ans;
}
